#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "word_map.h"

static inline int
max(int a, int b)
{
    return a > b ? a : b;
}

static WordMap *
word_map_new_node(const char *str, WordMap *left, WordMap *right)
{
    int length;
    WordMap *map;

    map = (WordMap *) malloc(sizeof(WordMap));
    if (map == NULL)
        return NULL;

    if (str != NULL) {
        length = strlen(str);
        map->str = (char *) malloc(sizeof(char) * (length + 1));
        if (map->str == NULL)  {
            free(map);
            return NULL;
        }

        strncpy(map->str, str, length + 1); 
    } else
        map->str = NULL;

    map->left = left;
    map->right = right;
    return map;
}

WordMap *
word_map_new()
{
    /* return word_map_new_node(NULL, NULL, NULL); */
    return NULL;
}

void
word_map_free(WordMap *map)
{
    if (map != NULL) {
        free(map->str);
        word_map_free(map->left);
        word_map_free(map->right);
        free(map);
    }
}

static int
word_map_traverse_to_insertion(WordMap **map, const char *str)
{
    int cmp;
    WordMap *map_ptr;

    if (*map == NULL)
        return 0;

    map_ptr = *map;
    while (map_ptr != NULL) {
        cmp = strcmp(str, map_ptr->str);
        if (cmp < 0) {
            if (map_ptr->left != NULL)
                map_ptr = map_ptr->left;
            else
                goto traverse_end;
        } else if (cmp > 0) {
            if (map_ptr->right != NULL)
                map_ptr = map_ptr->right;
            else
                goto traverse_end;
        } else {
            *map = NULL;
            return 0;
        }
    }

traverse_end:
    *map = map_ptr;
    return cmp;
}

int
word_map_add(WordMap **map, const char *str)
{
    WordMap *map_ptr;
    int cmp;

    if (map == NULL || str == NULL)
        return 1;

    /* Empty tree case */
    if (*map == NULL) {
        *map = word_map_new_node(str, NULL, NULL);
        return 0;
    }

    map_ptr = *map;
    cmp = word_map_traverse_to_insertion(&map_ptr, str);
    if (map_ptr == NULL)
        return 1; /* str is already in tree */

    assert(cmp != 0);
    if (cmp < 0)
        map_ptr->left = word_map_new_node(str, NULL, NULL);
    else if (cmp > 0)
        map_ptr->right = word_map_new_node(str, NULL, NULL);

    return 0;
}
